package com.lc.hot100.lc322;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
	}
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = 1; i <= amount; i ++) {
        	for (int j = 0; j < coins.length; j ++) {
        		if (i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE) {
                	f[i] = Math.min(f[i], f[i - coins[j]] + 1);
        		}
        	}
        }
        System.out.println(Arrays.toString(f));
        return f[amount] == Integer.MAX_VALUE ? - 1 : f[amount];
    }
}
